//Given an array of non-negative integers nums, you are initially positioned at 
//the first index of the array. 
//
// Each element in the array represents your maximum jump length at that positio
//n. 
//
// Your goal is to reach the last index in the minimum number of jumps. 
//
// You can assume that you can always reach the last index. 
//
// 
// Example 1: 
//
// 
//Input: nums = [2,3,1,1,4]
//Output: 2
//Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 
//step from index 0 to 1, then 3 steps to the last index.
// 
//
// Example 2: 
//
// 
//Input: nums = [2,3,0,1,4]
//Output: 2
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 105 
// 
// Related Topics 贪心算法 数组 
// 👍 973 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Jump Game II
class P45JumpGameIi {
    public static void main(String[] args) {
        Solution solution = new P45JumpGameIi().new Solution();
        // TO TEST
        Assert.assertEquals(solution.jump(new int[]{2, 3, 1, 1, 4}), 2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int jump(int[] nums) {
            int[] dp = new int[nums.length];
            for (int i = 1; i < dp.length; i++) {
                dp[i] = Integer.MAX_VALUE;
            }
            for (int i = 0; i < nums.length; i++) {
                for (int j = 1; j <= nums[i]; j++) {
                    if (i + j > nums.length - 1) {
                        dp[nums.length - 1] = Math.min(dp[i] + 1, dp[nums.length - 1]);
                    } else {
                        dp[i + j] = Math.min(dp[i] + 1, dp[i + j]);
                    }
                }
            }
            return dp[nums.length - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}